package algorithm_demo.demo01;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Api
 * @date 2023/2/5 18:15
 */
public class Code35_LevelOrderBottom {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static List<String> binaryTreePaths(TreeNode root) {
        List<String> ans = new ArrayList<String>();
        if (root == null) {
            return ans;
        }
        List<Integer> path = new ArrayList<Integer>();
        process(root, path, ans);
        return ans;
    }

    public static void process(TreeNode x, List<Integer> path, List<String> ans) {
        if (x.left == null && x.right == null) {
            path.add(x.val);
            String temp = "";
            for (Integer j : path) {
                temp = temp + j + "->";
            }
            temp = temp.substring(0, temp.length() - 2);
            ans.add(temp);
            path.remove(path.size()-1);
        }
        //x是非叶子节点时：
        path.add(x.val);
        if (x.left != null){
            process(x.left, path, ans);
        }
        if(x.right != null){
            process(x.right, path, ans);
        }
        path.remove(path.size()-1);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.right = null;
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.right.left = new TreeNode(5);
        root.right.right.right = new TreeNode(1);
        List<String> lists = binaryTreePaths(root);
        System.out.println(lists);
    }
}
